package Sort;
/*
希尔排序
它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
*4.1 算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，i<j，tk=1；

（2）按增量序列个数k，对序列进行k 趟排序；

（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m（m=length/ti） 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

//算法分析
（1）希尔排序的空间复杂度为O(1)，是一种原地排序算法。

（2）希尔排序不是一种不稳定的排序算法。多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

（3）选择排序的最好时间复杂度为O(n)、最坏时间复杂度都是O(n^2)，平均时间复杂度为O(n^1.3)。

* */
public class ShellSort {
    //4、希尔排序：
    static void shell(int[] a){
        int len = a.length;

        //希尔排序的关键在于设置增量，这里我们动态设置一个增量
        int gap=1;
        while(gap<len/3){
            gap=gap*3+1;
        }

        int temp;
        for(;gap>0;gap=(int) Math.floor(gap/3)){
            for(int i=gap;i<len;i++){
                temp = a[i];
                int j=i-gap;
                for(;j>=0 && a[j]>temp;j-=gap){
                    a[j+gap]=a[j];
                }
                a[j+gap]=temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321,9,3};
        shell(nums);
        for (int i:nums
        ) {
            System.out.println(i);
        }
    }

}
